import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created by L.jp
 * Description:输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
 * User: 86189
 * Date: 2021-12-16
 * Time: 13:25
 */
//解题思路：
//这道题整体解决思路很多，可以使用stack，可以递归，也可以将数据保存数组，逆序数组
class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public int[] printListFromTailToHead(ListNode listNode) {
        //从尾到头逆序返回链表，那么就可以采用栈的先进后出的原理来实现
        /*
        Stack<Integer> stack=new Stack<>();
        ArrayList<Integer> list=new ArrayList<>();
        if(listNode==null){
            return list;
        }
        while(listNode!=null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        while(!stack.isEmpty()){
            list.add(stack.pop());
        }
        return list;

         */

        //数组逆序的方法
        /*
        ArrayList<Integer> list=new ArrayList<>();
        while(listNode!=null){
            list.add(listNode.val);
            listNode=listNode.next;
        }
        int i=0;
        int j=list.size()-1;
        while(i<j){
            Integer tmp=list.get(i);//链表存放的是Integer类型，不是整型
            list.set(i,list.get(j));//利用set方法，而不是直接set(i)=set(j),这样是非法的
            list.set(j,tmp);
            i++;
            j--;
        }
        return list;

         */

        //递归方法
        ArrayList<Integer> list=new ArrayList<>();
        int[] array=new int[list.size()];
        printListFromTailToHeadHelper(list,listNode);
        for(int i=0;i<array.length;i++){
            array[i]=list.get(i);
        }
        return array;


    }
    //递归链表
    public void printListFromTailToHeadHelper(ArrayList<Integer>list,ListNode listNode){
        if(listNode==null){
            return;
        }
        printListFromTailToHeadHelper(list,listNode.next);
        list.add(listNode.val);
    }
}
